package newcoder;

import java.util.Arrays;
import java.util.PriorityQueue;

public class NC164 {
    public static void main(String[] args) {
        int[] a = new int[]{1,4,7,5,6};
        if (a.length <= 1) System.out.println(a.length);
        PriorityQueue<Integer>  p = new PriorityQueue<>();
        p.add(4);
        p.add(6);
        p.add(2);

        int[] mem = new int[a.length];
        mem[0] = a[0];
        int lenLIS = 1;

        for (int i = 1; i < a.length; i++) {
            int num = a[i];
            // search mem[0, lenLIS-1]
            int result = Arrays.binarySearch(mem, 0, lenLIS, num);
            if (result >= 0) continue;  // found, skip
            // result = -insertionPoint - 1
            int insertionPoint = -1-result;
            mem[insertionPoint] = num;
            if (insertionPoint == lenLIS) lenLIS++;
        }

        System.out.println(lenLIS);
    }
}
